// https://leetcode.cn/problems/basic-calculator/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int calculate(string s) {
        stack<int> sum;
        stack<int> ops;
        int res = 0;
        int sign = 1;
        int i = 0;

        while (i < s.size()) {
            char ch = s[i];

            if (ch == ' ') {
                i++;
                continue;
            } else if (ch >= '0' && ch <= '9') {
                int num = 0;
                while (i < s.size() && s[i] >= '0' && s[i] <= '9') {
                    num = (10 * num + (s[i] - '0'));
                    i++;
                }
                res += num * sign;
                continue;
            } else if (ch == '-') {
                sign = -1;
                i++;
            } else if (ch == '+') {
                sign = 1;
                i++;
            } else if (ch == '(') {
                sum.push(res);
                ops.push(sign);
                res = 0;
                sign = 1;
                i++;
            } else if (ch == ')') {
                res = sum.top() + res * ops.top();
                sum.pop();
                ops.pop();
                i++;
            }
        }
        return res;
    }
};